We propose a way of associating to each finitely generated monoid orsemigroup a formal language, called its loop problem. In the case of a group,the loop problem is essentially the same as the word problem in the sense ofcombinatorial group theory. Like the word problem for groups, the loop problemis regular if and only if the monoid is finite. We study also the case in whichthe loop problem is context-free, showing that a celebrated group-theoreticresult of Muller and Schupp extends to describe completely simple semigroupswith context-free loop problems. We consider also right cancellative monoids,establishing connections between the loop problem and the structural theory ofthese semigroups by showing that the syntactic monoid of the loop problem isthe inverse hull of the monoid.
展开▼
